//给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
//
// 示例 1：
//
// 输入: "babad"
//输出: "bab"
//注意: "aba" 也是一个有效答案。
//
//
// 示例 2：
//
// 输入: "cbbd"
//输出: "bb"
//
// Related Topics 字符串 动态规划


package leetcode.editor.cn;

public class P5LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new P5LongestPalindromicSubstring().new Solution();
        //TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String longestPalindrome(String s) {
            if (s.length() < 2) {
                return s;
            }
            int l = 0;
            int r = 0;
            int[] ls = {0, 0};
            for (int i = 0; i < s.length(); i++) {
                l = i;
                r = maxSame(s, i);
                while (l >= 0 && r < s.length()) {
                    if (s.charAt(l) == s.charAt(r)) {
                        l--;
                        r++;
                    } else {
                        break;
                    }
                }
                int length = r - l - 1;
                if (length > ls[1] - ls[0] + 1) {
                    ls[0] = l + 1;
                    ls[1] = r - 1;
                }
            }
            return s.substring(ls[0], ls[1] + 1);
        }

        public int maxSame(String s, int i) {
            int max = i;
            while (max < s.length() && s.charAt(max) == s.charAt(i)) {
                max++;
            }
            max--;
            return max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
